package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.DenseGraph;
import cn.initcap.algorithm.graph.DenseWeightedGraph;
import cn.initcap.algorithm.graph.Edge;
import cn.initcap.algorithm.graph.SparseGraph;
import cn.initcap.algorithm.graph.SparseWeightedGraph;
import java.util.List;

/**
 * @author initcap
 * @date Created in 1/20/19 5:04 PM.
 */
public class Main {

    public static void main(String[] args) {
        testBellmanFord();
        testDijkstra();
        testKruskalMSTAndLazyPrimMSTAndPrimMSTFaster();
        testLazyPrimMSTAndPrimMSTFaster();
        testLazyPrimMST();
        testReadWeightedGraph();

        long start = System.currentTimeMillis();
        testShortestPath();
        long end = System.currentTimeMillis();
        System.out.println("【测试无权图最短路径算法】总耗时： " + (end - start) + "ms");

        long start1 = System.currentTimeMillis();
        testPath();
        long end1 = System.currentTimeMillis();
        System.out.println("【测试寻路算法】总耗时： " + (end1 - start1) + "ms");

        long start2 = System.currentTimeMillis();
        testGraphComponent();
        long end2 = System.currentTimeMillis();
        System.out.println("【测试图的联通分量算法】总耗时： " + (end2 - start2) + "ms");

        printReadTxtGraph();
    }

    /**
     * 测试无权图最短路径算法
     */
    private static void testShortestPath() {
        SparseGraph g = new SparseGraph("algorithm/testG.txt", false);
        g.show();

        // 比较使用深度优先遍历和广度优先遍历获得路径的不同
        // 广度优先遍历获得的是无权图的最短路径
        Path dfs = new Path(g, 0);
        System.out.print("DFS : ");
        dfs.showPath(6);

        ShortestPath bfs = new ShortestPath(g, 0);
        System.out.print("BFS : ");
        bfs.showPath(6);

        System.out.println();

        SparseGraph g2 = new SparseGraph("algorithm/testG1.txt", false);
        g2.show();

        // 比较使用深度优先遍历和广度优先遍历获得路径的不同
        // 广度优先遍历获得的是无权图的最短路径
        Path dfs2 = new Path(g2, 0);
        System.out.print("DFS : ");
        dfs2.showPath(3);

        ShortestPath bfs2 = new ShortestPath(g, 0);
        System.out.print("BFS : ");
        bfs2.showPath(3);
    }

    /**
     * 测试寻路算法
     */
    private static void testPath() {
        SparseGraph g = new SparseGraph("algorithm/testG.txt", false);
        g.show();
        System.out.println();

        Path path = new Path(g, 0);
        System.out.println("Path from 0 to 6 : ");
        path.showPath(6);
    }

    /**
     * 测试图的联通分量算法
     */
    private static void testGraphComponent() {
        // TestG1.txt
        SparseGraph g1 = new SparseGraph("algorithm/testG1.txt", false);
        Components component1 = new Components(g1);
        System.out.println("TestG1.txt, Component Count: " + component1.count());
        System.out.println();

        // TestG2.txt
        SparseGraph g2 = new SparseGraph("algorithm/testG2.txt", false);
        Components component2 = new Components(g2);
        System.out.println("TestG2.txt, Component Count: " + component2.count());
    }

    /**
     * 使用两种图的存储方式读取testG1.txt文件
     */
    private static void printReadTxtGraph() {
        SparseGraph g1 = new SparseGraph("algorithm/testG1.txt", false);
        System.out.println("test G1 in Sparse Graph:");
        g1.show();

        System.out.println();

        DenseGraph g2 = new DenseGraph("algorithm/testG1.txt", false);
        System.out.println("test G1 in Dense Graph:");
        g2.show();

        System.out.println();

        // 使用两种图的存储方式读取testG2.txt文件
        SparseGraph g3 = new SparseGraph("algorithm/testG2.txt", false);
        System.out.println("test G2 in Sparse Graph:");
        g3.show();

        System.out.println();

        DenseGraph g4 = new DenseGraph("algorithm/testG2.txt", false);
        System.out.println("test G2 in Dense Graph:");
        g4.show();
    }

    private static void testBellmanFord() {
        String filename = "algorithm/testG8.txt";
        int v = 5;
        SparseWeightedGraph<Integer> g = new SparseWeightedGraph<>(filename, true);
        System.out.println("Test Bellman-Ford:\n");

        int s = 0;
        BellmanFord<Integer> bellmanFord = new BellmanFord<Integer>(g, s);
        if (bellmanFord.negativeCycle()) {
            System.out.println("The graph contain negative cycle!");
        } else {
            for (int i = 0; i < v; i++) {
                if (i == s) {
                    continue;
                }

                if (bellmanFord.hasPathTo(i)) {
                    System.out.println("Shortest Path to " + i + " : " + bellmanFord.shortestPathTo(i));
                    bellmanFord.showPath(i);
                } else {
                    System.out.println("No Path to " + i);
                }

                System.out.println("----------");
            }
        }
    }

    private static void testDijkstra() {
        String filename = "algorithm/testG7.txt";
        int v = 5;

        SparseWeightedGraph<Integer> g = new SparseWeightedGraph<>(filename, true);
        // Dijkstra最短路径算法同样适用于有向图
        System.out.println("Test Dijkstra:\n");
        Dijkstra<Integer> dij = new Dijkstra<>(g, 0);
        for (int i = 1; i < v; i++) {
            if (dij.hasPathTo(i)) {
                System.out.println("Shortest Path to " + i + " : " + dij.shortestPathTo(i));
                dij.showPath(i);
            } else {
                System.out.println("No Path to " + i);
            }
            System.out.println("----------");
        }
    }

    /**
     * 测试lazyPrim和Prim优化的和Kruskal算法的性能
     */
    private static void testKruskalMSTAndLazyPrimMSTAndPrimMSTFaster() {
        String filename1 = "algorithm/testG3.txt";

        String filename2 = "algorithm/testG4.txt";

        String filename3 = "algorithm/testG5.txt";

        String filename4 = "algorithm/testG6.txt";

        // 文件读取
        SparseWeightedGraph<Double> g1 = new SparseWeightedGraph<>(filename1, false);
        System.out.println(filename1 + " load successfully.");

        SparseWeightedGraph<Double> g2 = new SparseWeightedGraph<>(filename2, false);
        System.out.println(filename2 + " load successfully.");

        SparseWeightedGraph<Double> g3 = new SparseWeightedGraph<>(filename3, false);
        System.out.println(filename3 + " load successfully.");

        SparseWeightedGraph<Double> g4 = new SparseWeightedGraph<>(filename4, false);
        System.out.println(filename4 + " load successfully.");

        System.out.println();


        long startTime, endTime;

        // Test Lazy Prim MST
        System.out.println("Test Lazy Prim MST:");

        startTime = System.currentTimeMillis();
        LazyPrimMst<Double> lazyPrimMst1 = new LazyPrimMst<>(g1);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G3: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        LazyPrimMst<Double> lazyPrimMst2 = new LazyPrimMst<>(g2);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G4: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        LazyPrimMst<Double> lazyPrimMst3 = new LazyPrimMst<>(g3);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G5: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        LazyPrimMst<Double> lazyPrimMst4 = new LazyPrimMst<>(g4);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G6: " + (endTime - startTime) + "ms.");

        System.out.println();


        // Test Prim MST
        System.out.println("Test Prim MST:");

        startTime = System.currentTimeMillis();
        PrimMst<Double> primMst1 = new PrimMst<>(g1);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G3: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        PrimMst<Double> primMst2 = new PrimMst<>(g2);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G4: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        PrimMst<Double> primMst3 = new PrimMst<>(g3);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G5: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        PrimMst<Double> primMst4 = new PrimMst<>(g4);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G6: " + (endTime - startTime) + "ms.");

        System.out.println();

        // Test Kruskal MST
        System.out.println("Test Kruskal MST:");

        startTime = System.currentTimeMillis();
        KruskalMst<Double> kruskalMst1 = new KruskalMst<>(g1);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G3: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        KruskalMst<Double> kruskalMst2 = new KruskalMst<>(g2);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G4: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        KruskalMst<Double> kruskalMst3 = new KruskalMst<>(g3);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G5: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        KruskalMst<Double> kruskalMst4 = new KruskalMst<>(g4);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G6: " + (endTime - startTime) + "ms.");

        System.out.println();
    }

    /**
     * 测试我们实现的两种Prim算法的性能差距
     * 可以看出这一节使用索引堆实现的Prim算法优于上一小节的Lazy Prim算法
     */
    private static void testLazyPrimMSTAndPrimMSTFaster() {
        String filename1 = "algorithm/testG3.txt";

        String filename2 = "algorithm/testG4.txt";

        String filename3 = "algorithm/testG5.txt";

        String filename4 = "algorithm/testG6.txt";

        // 文件读取
        SparseWeightedGraph<Double> g1 = new SparseWeightedGraph<>(filename1, false);
        System.out.println(filename1 + " load successfully.");

        SparseWeightedGraph<Double> g2 = new SparseWeightedGraph<>(filename2, false);
        System.out.println(filename2 + " load successfully.");

        SparseWeightedGraph<Double> g3 = new SparseWeightedGraph<>(filename3, false);
        System.out.println(filename3 + " load successfully.");

        SparseWeightedGraph<Double> g4 = new SparseWeightedGraph<>(filename4, false);
        System.out.println(filename4 + " load successfully.");

        System.out.println();


        long startTime, endTime;

        // Test Lazy Prim MST
        System.out.println("Test Lazy Prim MST:");

        startTime = System.currentTimeMillis();
        LazyPrimMst<Double> lazyPrimMst1 = new LazyPrimMst<>(g1);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G3: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        LazyPrimMst<Double> lazyPrimMst2 = new LazyPrimMst<>(g2);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G4: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        LazyPrimMst<Double> lazyPrimMst3 = new LazyPrimMst<>(g3);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G5: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        LazyPrimMst<Double> lazyPrimMst4 = new LazyPrimMst<>(g4);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G6: " + (endTime - startTime) + "ms.");

        System.out.println();


        // Test Prim MST
        System.out.println("Test Prim MST:");

        startTime = System.currentTimeMillis();
        PrimMst<Double> primMst1 = new PrimMst<>(g1);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G3: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        PrimMst<Double> primMst2 = new PrimMst<>(g2);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G4: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        PrimMst<Double> primMst3 = new PrimMst<>(g3);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G5: " + (endTime - startTime) + "ms.");

        startTime = System.currentTimeMillis();
        PrimMst<Double> primMst4 = new PrimMst<>(g4);
        endTime = System.currentTimeMillis();
        System.out.println("Test for G6: " + (endTime - startTime) + "ms.");

        System.out.println();
    }

    private static void testLazyPrimMST() {
        String filename = "algorithm/testG3.txt";
        SparseWeightedGraph<Double> g = new SparseWeightedGraph<>(filename, false);

        // Test Lazy Prim MST
        System.out.println("Test Lazy Prim MST:");
        LazyPrimMst<Double> lazyPrimMst = new LazyPrimMst<>(g);
        List<Edge<Double>> mst = lazyPrimMst.mstEdges();
        for (int i = 0; i < mst.size(); i++) {
            System.out.println(mst.get(i));
        }
        System.out.println("The MST weight is: " + lazyPrimMst.result());

        System.out.println();
    }

    /**
     * 测试通过文件读取图的信息
     */
    private static void testReadWeightedGraph() {
        // 使用两种图的存储方式读取testG3.txt文件
        String filename = "algorithm/testG3.txt";
        SparseWeightedGraph<Double> g1 = new SparseWeightedGraph<>(filename, false);
        System.out.println("test G3 in Sparse Weighted Graph:");
        g1.show();

        System.out.println();

        DenseWeightedGraph<Double> g2 = new DenseWeightedGraph<Double>(filename, false);
        System.out.println("test G3 in Dense Graph:");
        g2.show();

        System.out.println();
    }

}
